package net.tp.algo.sort;

/**
 *
 * <p>QuickSort</p>
 *
 * <p>This is fast implementation if there is no duplicate value. If there are many duplicate values, this implementation
 * may run in quadratic time. In case of many duplicate values, use three-way quicksort or four-way quicksort.</p>
 *
 * @author Trung Phan
 */
public class QuickSort {

    public static void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    public static void sort(int[] a, int lo, int hi) {

        while (lo < hi) {
            int pivot = pivot(a, lo, hi);
            int pv = a[pivot];
            swap(a, lo, pivot);

            int lt = lo+1, gt = hi;
            while (true) {
                while (lt <= gt && a[lt] <= pv) lt++;
                while (lt <= gt && a[gt] > pv) gt--;
                if (lt > gt) break;
                swap(a, lt, gt);
            }

            swap(a, lo, lt-1);
            lt--;

            if (lt - lo <= hi - gt) {
                sort(a, lo, lt-1);
                lo = gt+1;
            }
            else {
                sort(a, gt+1, hi);
                hi = lt-1;
            }
        }

    }

    private static void swap(int[] a, int i, int j) {
        if (i != j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }


    /**
     * <p>Select pivot.</p>
     *
     * <p>There are many strategies to select the pivot. This implementation uses "the Ninther" strategy.</p>
     *
     * @param a
     * @param lo
     * @param hi
     * @return the index of the pivot
     */
    private static int pivot(int[] a, int lo, int hi) {

        int mid = (lo + hi) >>> 1;

        if (hi - lo < 9) {
            return medianOf3(a, lo, mid, hi);
        }
        else {
            int d = (lo + mid) >>> 2;
            return medianOf3(a,
                    medianOf3(a, lo, lo+d, lo+2*d),
                    medianOf3(a, mid-d, mid, mid+d),
                    medianOf3(a, hi-2*d, hi-d, hi)
                    );
        }
    }

    private static int medianOf3(int[] a, int lo, int mid, int hi) {
        if (a[lo] <= hi) {
            if (a[mid] <= a[lo]) return lo;
            else return a[mid] <= a[hi] ? mid : hi;
        }
        else {
            if (a[mid] <= a[hi]) return hi;
            else return a[mid] <= a[lo] ? mid : lo;
        }
    }


}
